package org.algorithm.biubiu.wheel_1.链表;

import org.algorithm.biubiu.wheel_1.common.ListNode;
import org.junit.Test;

import java.util.HashMap;
import java.util.LinkedHashMap;

/***
 *
 *  和为0 包括但不限定：    正整数之间想减和为0， 正负相加和为0
 *
 * 参考地址： https://leetcode-cn.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list/
 */
public class 删除和为0的连续节点 {


    @Test
    public void test(){
        removeZeroSumSublists(ListNode.build(1,3,2,-3,-2,5,5,-5,1));
    }

    public ListNode removeZeroSumSublists(ListNode head) {
        if(head==null){
            return null;
        }
        HashMap<Integer,ListNode> summation_node = new LinkedHashMap<>();
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        ListNode dummy = dummyNode;
        int summation = 0;
        while(dummy!=null){
            summation   = summation+dummy.val;
            summation_node.put(summation,dummy);
            dummy = dummy.next;
        }

        dummy = dummyNode;
        summation = 0;
        while(dummy!=null){
            summation   = summation+dummy.val;
            ListNode node =  summation_node.get(summation);
            dummy.next = node.next;
            dummy = dummy.next;
        }

        return dummyNode.next;
    }
}
